<?php

/*
 * 二叉查找树
 * @package
 * @author     wanglei@wyzc.com
 * @version    $Id$
 */

class node {
	public $id;
	public $data;
	public $left;
	public $right;
	public $parent;

	public function __construct($id, $data, $left = null, $right = null, $parent = null) {
		$this->id     = $id;
		$this->data   = $data;
		$this->left   = $left;
		$this->right  = $right;
		$this->parent = $parent;
	}
}


class searchTree {

	//根节点
	private $root;

	public function __construct(node $node) {
		$this->root = $node;
	}

	/**
	 * 插入节点
	 * @param node $node
	 * @return bool
	 */
	public function append(node $node) {
		$current = $this->root;
		while ($current) {
			if ($current->id == $node->id) break;
			if ($current->id > $node->id) {
				//如何小于当前节点，插在左边
				if ($current->left == null) {
					$current->left = $node;
					$node->parent  = $current;
					break;
				}
				$current = $current->left;
			} else {
				//如何大于当前节点，插在右边
				if ($current->right == null) {
					$current->right = $node;
					$node->parent   = $current;
					break;
				}
				$current = $current->right;
			}
		}
		return false;
	}

	/**
	 * 先序查找节点
	 * @param      $id
	 * @param null $start
	 * @return bool|node|null
	 */
	public function find($id, $start = null) {
		if ($start == null) $start = $this->root;
		if ($start->id == $id) {
			return $start;
		} elseif ($start->id > $id) {
			if ($start->left) return $this->find($id, $start->left);
		} else {
			if ($start->right) return $this->find($id, $start->right);
		}
		return false;
	}

	/**
	 * 先序遍历
	 * 根->左->右
	 * @param      $callback
	 * @param null $start
	 */
	public function travers_pre($callback, $start = null) {
		if ($start == null) $start = $this->root;
		$callback($start);
		if ($start->left) $this->travers_pre($callback, $start->left);
		if ($start->right) $this->travers_pre($callback, $start->right);
	}

	/**
	 * 中序遍历
	 * 左->根->右
	 * @param      $callback
	 * @param null $start
	 */
	public function travers_middle($callback, $start = null) {
		if ($start == null) $start = $this->root;
		if ($start->left) $this->travers_middle($callback, $start->left);
		$callback($start);
		if ($start->right) $this->travers_middle($callback, $start->right);
	}


	/**
	 * 后序遍历
	 * 左->右->根
	 * @param      $callback
	 * @param null $start
	 */
	public function travers_behind($callback, $start = null) {
		if ($start == null) $start = $this->root;
		if ($start->left) $this->travers_behind($callback, $start->left);
		if ($start->right) $this->travers_behind($callback, $start->right);
		$callback($start);
	}

	/**
	 * 查找后继节点
	 * @param $node
	 * @return node
	 */
	public function successor($node) {
		//如果有右子树，右子树的最小值即为后继
		if ($node->right) {
			$current = $node->right;
			while ($current->left != null) {
				$current = $current->left;
			}
			return $current;
		}
		//如果没有右子树，根节点就是后继
		return $this->root;
	}

	/**
	 * 删除节点
	 * @param $id
	 * @return bool
	 * @throws Exception
	 */
	public function delete($id) {
		//查找要被删除的元素node
		$node = $this->find($id);
		//如果找到node
		if ($node) {
			/** 如果node是叶节点,让它的父节点指向null **/
			if ($node->left == null && $node->right == null) {
				if ($this->root == $node) {
					throw new Exception('不能删除唯一的根节点');
				} else {
					if ($node->parent->id > $node->id) {
						$node->parent->left = null;
					} else {
						$node->parent->right = null;
					}
				}
				return true;
			}
			/** 如果node的左右子树均不为空 **/
			if ($node->left != null && $node->right != null) {
				//找到node的后继节点successor
				$successor = $this->successor($node);
				//改变successor的父节点的指针
				if ($successor->parent->id > $successor->id) {
					$successor->parent->left = null;
				} else {
					$successor->parent->right = null;
				}
				//将node的值替换为successor的
				$node->id   = $successor->id;
				$node->data = $successor->data;
				return true;
			}

			/** 如果node只有一颗子树 **/
			$s = null; //s表示子树
			if ($node->left == null) $s = $node->right;
			if ($node->right == null) $s = $node->left;
			if ($this->root == $node) {
				$this->root = $s;
			} else {
				if ($node->parent->id > $node->id) {
					$node->parent->left = $s;
				} else {
					$node->parent->right = $s;
				}
			}
			return true;
	}
return false;
}

}

$tree = new searchTree(new node(100, '北京'));
$tree->append(new node(47, '河北'));
$tree->append(new node(102, '天津'));
$tree->append(new node(107, '厦门'));
$tree->append(new node(101, '江西'));
$tree->append(new node(58, '连云港'));
$tree->append(new node(46, '大连'));
//当前树结构
//                   北京(100)

//       河北(47)                天津(102)

// 大连(46)   连云港(58)   江西(101)      厦门(107)

/** 先序遍历 **/
$tree->travers_pre(function ($current) {
	echo $current->data . ' ';
});
//北京 河北 大连 连云港 天津 江西 厦门
echo PHP_EOL;

/** 中序遍历 **/
$tree->travers_middle(function ($current) {
	echo $current->data . ' ';
});
//大连 河北 连云港 北京 江西 天津 厦门
echo PHP_EOL;

/** 后序遍历 **/
$tree->travers_behind(function ($current) {
	echo $current->data . ' ';
});
//大连 连云港 河北 江西 厦门 天津 北京
echo PHP_EOL;

//删除北京
$node = $tree->delete(102);

/** 中序遍历 **/
$tree->travers_middle(function ($current) {
	echo $current->data . ' ';
});
//大连 河北 连云港 江西 天津 厦门
